import java.util.Arrays;

class Solution {
    public int[] smallestK(int[] arr, int k) {
        // 处理边界情况
        if (arr == null || arr.length == 0 || k <= 0) {
            return new int[0];
        }

        // 如果k大于等于数组长度，直接返回排序后的整个数组
        if (k >= arr.length) {
            Arrays.sort(arr);
            return arr;
        }

        // 使用快速选择算法找到第k小的元素，并将数组分区
        quickSelect(arr, 0, arr.length - 1, k);

        // 返回前k个元素
        return Arrays.copyOf(arr, k);
    }

    private void quickSelect(int[] arr, int left, int right, int k) {
        if (left >= right) {
            return;
        }

        // 分区并获取分区点位置
        int pivotIndex = partition(arr, left, right);
        int count = pivotIndex - left + 1; // 左半部分（包括pivot）的元素数量

        if (k < count) {
            // 第k小的元素在左半部分，继续在左半部分查找
            quickSelect(arr, left, pivotIndex - 1, k);
        } else {
            // 第k小的元素在右半部分，继续在右半部分查找剩余的k-count个
            quickSelect(arr, pivotIndex + 1, right, k - count);
        }
    }

    // 分区函数，将数组分为两部分，左边部分小于等于pivot，右边部分大于pivot
    private int partition(int[] arr, int left, int right) {
        int pivot = arr[right]; // 选择最后一个元素作为基准值
        int i = left - 1; // 指向最后一个小于等于pivot的元素

        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }

        // 将基准值放到正确的位置
        swap(arr, i + 1, right);
        return i + 1; // 返回基准值的位置
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 主方法，用于测试
    public static void main(String[] args) {
        Solution solution = new Solution();

        // 测试用例1
        int[] arr1 = {3, 2, 1};
        int k1 = 2;
        int[] result1 = solution.smallestK(arr1, k1);
        System.out.println("测试用例1: 输入数组 = [3, 2, 1], k = 2");
        System.out.println("输出: " + Arrays.toString(result1)); // 应该输出 [1, 2]

        // 测试用例2
        int[] arr2 = {0, 1, 2, 1};
        int k2 = 1;
        int[] result2 = solution.smallestK(arr2, k2);
        System.out.println("\n测试用例2: 输入数组 = [0, 1, 2, 1], k = 1");
        System.out.println("输出: " + Arrays.toString(result2)); // 应该输出 [0]

        // 测试用例3：k等于数组长度
        int[] arr3 = {5, 3, 8, 2, 7};
        int k3 = 5;
        int[] result3 = solution.smallestK(arr3, k3);
        System.out.println("\n测试用例3: 输入数组 = [5, 3, 8, 2, 7], k = 5");
        System.out.println("输出: " + Arrays.toString(result3)); // 应该输出 [2, 3, 5, 7, 8]

        // 测试用例4：空数组
        int[] arr4 = {};
        int k4 = 3;
        int[] result4 = solution.smallestK(arr4, k4);
        System.out.println("\n测试用例4: 输入数组 = [], k = 3");
        System.out.println("输出: " + Arrays.toString(result4)); // 应该输出 []
    }
}